#include <sys/types.h>
#include <sys/ipc.h> 
#include <sys/shm.h>
#include <sys/wait.h>
#include <unistd.h>

#include <iostream>
#include <cstring>
#include <cstdlib>

using namespace std;

string palavra1, palavra2;
int linhas, colunas;

int position(int linha, int coluna) {
    int p = linha * (colunas + 1) + coluna;
    return p;
}

void insert(int* shm, int x, int linha, int coluna) {
    int p = position(linha, coluna);
    shm[p] = x;
}

int get(int* shm, int linha, int coluna) {
    int p = position(linha, coluna);
    return shm[p];
}

void set_limit(int* shm, int x, int linha) {
    insert(shm, x, linha, colunas);
}

int get_limit(int* shm, int linha) {
    return get(shm, linha-1, colunas);
}

void print(int* shm) {
    cout << "  ";
    for (int j = 0; j < colunas; j++) {
        cout << palavra1[j] << " ";
    }
    cout << endl;

    for (int i = 0; i < linhas; i++) {
        cout << palavra2[i] << " ";
        for (int j = 0; j < colunas; j++) {
            cout << get(shm, i, j) << " ";
        }
        cout << endl;
    }
}

int main() {
    int* shm;
    int shmid;
    key_t key;
    int size;

    int sou = 0;
    int linha, coluna;
    int limite, coluna_atual;
    
    int status = 0;

    // palavras
    cout << "Digite a primeira palavra: ";
    cin >> palavra1;
    palavra1 = '$' + palavra1;
    colunas = palavra1.size();

    cout << "Digite a segunda palavra: ";
    cin >> palavra2;
    palavra2 = '$' + palavra2;
    linhas = palavra2.size();

    // nome do segmento de memoria compartilhada
    key = 5678;

    // tamanho da regiao de memoria
    size = linhas * (colunas + 1);

    // criando o segmento
    shmid = shmget(key, size * sizeof(int), IPC_CREAT | 0666);
    if (shmid < 0) {
        cout << "erro" << endl;
        exit(1);
    }

    // acoplando o segmento ao espaco de dados
    shm = (int *) shmat(shmid, 0, 0);

    // inicializa a matriz de resposta
    for (linha = 0; linha < linhas; linha++) {
        insert(shm, 0, linha, 0);
    }

    for (coluna = 0; coluna < colunas + 1; coluna++) {
        insert(shm, 0, 0, coluna);
    }
    
    for (linha = 0; linha < linhas; linha++) {
        set_limit(shm, 1, linha);
    }    
    set_limit(shm, colunas, 0);

    // cria os filhos
    linha = 1;
    coluna = 1;
    while (linha < linhas) {
        sou = fork();
        if (sou == 0) {
            // codigo do filho
            limite = 1;
            coluna_atual = 1;

            while (coluna_atual < colunas) {
                // le seu limite de um processo (de linha == linha-1)
                limite = get_limit(shm, linha);

                // executa o algoritmo
                for (coluna = coluna_atual; coluna <= limite; coluna++) {
                    if (coluna == 0) {
                        break;
                    }

                    if (coluna == colunas) {
                        // escreve seu limite para que um processo (de linha == linha+1) possa ler
                        set_limit(shm, colunas, linha);
                        break;
                    }

                    char char_linha = palavra2[linha];
                    char char_coluna = palavra1[coluna];
                    
                    if (char_linha == char_coluna) {
                        int res = get(shm, linha-1, coluna-1);
                        insert(shm, res + 1, linha, coluna);
                    }
                    else {
                        int res = max(get(shm, linha, coluna-1), get(shm, linha-1, coluna));
                        insert(shm, res, linha, coluna);
                    }

                    // escreve seu limite para que um processo (de linha == linha+1) possa ler
                    set_limit(shm, coluna, linha);
                }
                coluna_atual = limite;
            }
            break;
        }
        else {
            // codigo do pai
            waitpid(sou, &status, 0);
        }
        linha = linha + 1;
    }

    // codigo que o pai executa depois que todos os filho terminam
    if (sou != 0) {
        print(shm);

        string palavra = "";
        linha = linhas - 1;
        coluna = colunas - 1;

        while (get(shm, linha, coluna) != 0) {
            if (get(shm, linha, coluna - 1) == get(shm, linha, coluna)) {
                coluna -= 1;
            }    
            else {
                palavra = palavra1[coluna] + palavra;
                linha -= 1;
                coluna -= 1; 
            }
        }
        cout << "Resposta: " << palavra << endl;
        
        // desacoplando o segmento
        if (shmdt(shm) == -1) {
            cout << "erro2" << endl;
            exit(1);
        }
    }

    return 0;
}
